﻿// 1799. N 次操作后的最大分数和.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cmath>


using namespace std;

/*
https://leetcode.cn/problems/maximize-score-after-n-operations/description/

给你 nums ，它是一个大小为 2 * n 的正整数数组。你必须对这个数组执行 n 次操作。
在第 i 次操作时（操作编号从 1 开始），你需要：

选择两个元素 x 和 y 。
获得分数 i * gcd(x, y) 。
将 x 和 y 从 nums 中删除。
请你返回 n 次操作后你能获得的分数和最大为多少。
函数 gcd(x, y) 是 x 和 y 的最大公约数。



示例 1：
输入：nums = [1,2]
输出：1
解释：最优操作是：
(1 * gcd(1, 2)) = 1


示例 2：
输入：nums = [3,4,6,8]
输出：11
解释：最优操作是：
(1 * gcd(3, 6)) + (2 * gcd(4, 8)) = 3 + 8 = 11

示例 3：
输入：nums = [1,2,3,4,5,6]
输出：14
解释：最优操作是：
(1 * gcd(1, 5)) + (2 * gcd(2, 4)) + (3 * gcd(3, 6)) = 1 + 4 + 9 = 14


提示：

1 <= n <= 7
nums.length == 2 * n
1 <= nums[i] <= 106
*/

class Solution {
public:

    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }

    int countOne(int x) {
        int ret = 0;
        while (x != 0) {
            if (x & 1) ret++;
            x >>= 1;
        }

        return ret;
    }
    int hashOne[1 << 14];
    int trans[14][14];
    int gcdTrans(vector<int>& nums) {
        for (int i = 0; i < nums.size(); i++) {
            for (int j = i + 1; j < nums.size(); j++) {
                //cout << "gcdTrans 0 i = " << i << ". j = " << j << endl;
                trans[i][j] = gcd(nums[i],nums[j]);
                //cout << "gcdTrans 1 i = " << i << ". j = " << j << endl;
            }
        }

        return 0;
    }
    
    int maxScore(vector<int>& nums) {
        int dp[1 << 14];
        memset(dp,0,sizeof dp);
        int len = nums.size();

        for (int i = 0; i < (1 << len); i++) {
            hashOne[i] = countOne(i);
            //printf("hashOne[%d] = %d \n", i, hashOne[i]);
        }
        gcdTrans(nums);

        for (int state = 0; state < 1 << len; state++) {
            for (int i = 0; i < len; i++) {
                for (int j = i+1; j < len; j++) {
                    if (i != j && ((state >> i) & 1) && ((state >> j) & 1)) {
                        int prev = state ^ (1 << i);    prev = prev ^ (1 << j);
                        dp[state] = max(dp[state], dp[prev] + (hashOne[prev] + 2) / 2 *trans[i][j]);
                    }
                }
            }
        }

        //cout << dp[(1<<len)-1] << endl;

        return dp[(1 << len) - 1];
    }
};



int main()
{
    Solution s;
    //vector<int> v{1,2};
    //vector<int> v{ 3, 4, 6, 8 };
    vector<int> v{ 1,2,3,4,5,6 };
    s.maxScore(v);


    return 0;
}
 